/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组
 */

/**
 * 1、给数组排序
 * 2、遍历数组，从0遍历到length-2（为什么）？防止越界
 * 3、如果当前的数字等于前一个数字，则跳过这个数（为什么）？防止有重复结果
 * 4、如果数字不同，则设置start=i+1，end=length-1，查看i，start，end三个数的和比零大还是小，如果比零小，start++，
 * 如果比零大，end--，如果等于零，把三个数加入到结果数组里面
 * 5、返回结果
*/

var threeSum = function (nums) {
  const result = [];
  nums.sort((a, b) => {
    return a - b;
  });

  for (let i = 0; i < nums.length - 2; i++) {
    // 防止会越界，防止有重复结果
    if (i === 0 || nums[i] !== nums[i - 1]) {
      let start = i + 1;
      let end = nums.length - 1;
      // start 要比 end小
      while (start < end) {
        if (nums[i] + nums[start] + nums[end] === 0) {
          result.push([nums[i], nums[start], nums[end]]);
          start++;
          end--;
          // 也是为了防止有重复结果
          while (start < end && nums[start] === nums[start - 1]) {
            start++;
          }
          while (start < end && nums[end] === nums[end + 1]) {
            end--;
          }
        } else if (nums[i] + nums[start] + nums[end] < 0) {
          start++;
        } else if (nums[i] + nums[start] + nums[end] > 0) {
          end--;
        }
      }
    }
  }
  return result;
};
